In a digital communication system, the received data may be corrupted by noise or distortion. Consequently, the digital data obtained at the receiving station may not be an accurate replica of the transmitted data. One form of error correction to reduce such errors includes encoding the transmitted data to add redundancy before transmission.
Redundancy may be introduced, for example, by increasing the symbol rate. More specifically, error checking and error correcting codes may be appended to fixed-length blocks of source data, and the combination may then be sent at a higher data rate. Signal-space codes may also be used to add redundancy by converting the source data into line code. One signal-space code which has enjoyed wide-spread acceptance because of its superior performance is the trellis code, a convolution code best explained using a trellis diagram.
The encoded transmitted data may be decoded using a Viterbi algorithm that is a highly effective decoding method. The Viterbi decoding algorithm was developed in 1967 and is an optimum decoding method for carrying out maximum likelihood decoding. By taking an example of a convolution encoder, a simple Viterbi decoding algorithm will be described with reference to FIG. 1. FIG. 1, shows a block structure of a general convolution encoder consisting of a 2-bit shift register 11 and two adders 12 for modulo-2 adding. The outputs of the convolution encoder, G1 and G2, may be determined by the state of the shift register and input 13. Its outputs over time points are illustrated in the form of a trellis diagram in FIG. 2.
Referring to FIG. 2 the outputs of the convolution encoder according to time points are shown. In the trellis diagram in FIG. 2, each node shows a different state that the shift register 11 may have. Each solid line branch represents the transition when the input of the shift register 11 is 0. Each dotted line branch represents the transition when input of the shift register 11 is 1. Also, the numeral of each branch represents the value of G1 and G2 when a transition in the related branch has occurred. At this moment, as two paths are overlapped in each respective state, a Viterbi decoder selects only one of the two paths which has a possibility, while the path having no possibility is discarded. In this manner, maximum likelihood decoding is carried out. The selected path is called a survivor path and each state of the survivor path preserves information for the survivor path as much as the determined decision depth or truncation depth (referred to hereinafter as "L"). Therefore, decoding is performed by selecting the greatest possibility path from among the survivor paths and tracing it back.
FIG. 3 shows a Viterbi decoder which includes a Branch Metric Unit (BMU) 22 for calculating the branch metric units between received input of the BMU 22 and a reference value of each branch in the trellis diagram of FIG. 2. An Add-Compare-Select-Unit (ACSU) 23 selects a respective survivor path at each state of the branch and calculates a state value of the survivor path. The state value is output to a Normalizing Unit (NU) 24 and a Maximum Likelihood Value Detection Unit (MLVDU) 26. The Normalizing Unit (NU) 24 subtracts the maximum branch metric value from the output of the ACSU 23. A State Metric Memory (SMM) 25 stores the calculated state value of the ACSU 23. The MLVDU 26 detects the survivor path being most possible from the respective survivor paths of each state. A Path Memory (PM) 27 stores the information for the survivor path in each state and a Traceback Unit (TU) 28 performs traceback based on values output from the MLVDU 26.
As described in FIG. 4, the TU 28 consists of a path storage 31 that stores the survivor path as much as the decision depth "L" (i.e., 0, 1, 2, . . . L-2, L-1), a multiplexer 32 and a register 33 wherein the magnitude of the register accords with K (constraint length )-1, the magnitude of the path storage is M(=2.sup.K-1)*L (wherein M is a constant) and the multiplexer is an M:1 multiplexer.
The tracing of the TU 28 is performed using survivor path information which is pre-stored at each time unit. That is, when the survivor information of the state m.sub.j =a.sub.j b.sub.j at a time unit j is s.sub.mj, a state m.sub.j-1 =a.sub.j-1 b.sub.j-1 at a time unit j-1 of prior state on an associated survivor path is m.sub.j-1 =b.sub.j s.sub.mj. At this time, since b.sub.j =a.sub.j -1 and s.sub.mj =b.sub.j -1 are given from the structure of the convolution encoder, the prior state in decoding is determined by detecting a state having the minimum value per each time unit and using the survivor path information stored in the path storage 27 from that state having the minimum value. This process is repeatedly performed up to the decision depth (L).
FIG. 5 shows a structure for a trellis code interleaver used in Advanced Television Systems Committee 8 Vestigial SideBand (ATSC 8VSB). The trellis code interleaver of FIG. 5 has the input stage 41 for receiving interleaved data, the output stage 43 for the output of trellis-coded and pre-coded data to a mapper (not shown) that adjusts the level to match standard transmission and twelve trellis encoders and pre-coders 42#0 through 42#11 intervened between the input stage 41 and output stage 43.
Hereinafter, operation of the trellis code interleaver will be described. Interleaved byte data from the input stage 41 is processed per byte by the twelve trellis encoders and pre-coders 42#0-42#11 being convolution encoders. One byte data generates four encoded symbol data through one encoder. One symbol data is input into the trellis encoders and pre-coders 42#0-42#11 per two bits from the most significant bit. As each byte data is encoded by means of the respective one of the trellis encoders and pre-coders 42#0-42#11, byte data of multiples of twelve is necessary for twelve trellis encoders and pre-coders 42#0-42#11. For converting byte data into symbol data, four segment unit conversions are carried out so that the byte unit is decoded into a symbol unit.
FIG. 6 shows a structure for a trellis code deinterleaver which includes an input stage 51 for receiving equalized and phase-corrected symbols, an output stage 53 for the output trellis decoded data and twelve trellis decoders 52#0-52#11 intervened between the input stage 51 and output stage 53. Here, each respective trellis decoder 52#0-52#11 has the same structure as the decoder of FIG. 3. Thus, each has the same function and operation. In addition, each respective trellis decoder 52#0-52#11 operates with each symbol clock and outputs one byte of decoded data per one symbol clock after receiving the symbol data corresponding to the decision depth "L."
As illustrated in FIG. 5, since a transmission stage of GA 8VB performs twelve symbol intra-segment interleavings, a reception stage requires twelve associated trellis decoders. However, it is noted that one symbol of the twelve symbols from the symbol sequence input into the reception stage has significant meaning in decoding.
FIG. 7 is a timing chart for a symbol clock (A), a symbol data (B), and symbol data (C-E) to be input into the respective trellis decoders. As can be seen from the drawing, each trellis decoder has a time margin up to eleven symbols between symbol data input. Therefore, each respective trellis decoder could finish traceback before input of new data thereto. For symbol clock input (.function.s), it is possible to trace data up to the decision depth L=11 for .function.s and up to the decision depth L=22 for 2.function.s. To keep Segment Error Rate below 3*16-.sup.-10 at Signal-to-Ratio=10.4 dB according to Advanced Television System Committee Digital TV standards, the decision depth L=22 is preferred.
Each respective trellis decoder performs traceback for each symbol input to produce one symbol clock (two bit data). As the convolution deinterleaver associated with each trellis decoder processes input-data per byte unit, one trellis decoder must produce one byte data through four step traceback. However, tracing for each symbol input to get one byte of decoded data results in four times traceback at one byte to increase the path storage 27 in FIG. 4 by eighty-eight times. This accelerates transition frequency and increases power consumption in the Complementary Metal Oxide Semiconductor Application Specific Integrated Circuit (CMOS ASIC). Accordingly, as this increase of power consumption inevitably causes more heat to occur, particular packaging is necessary to prevent such heat, resulting in an increase in cost of ASIC manufacturing.
European Patent No. EP 0 661,840 describes a technique for decreasing the traceback length of the Viterbi decoder. The patent includes means for generating surviving branch data, storing the surviving branch data, initiating a first traceback of length "k" and initiating from the predetermined symbol an instant traceback length of k-m (m=0, 1, 2. . . k-1). Although this technique enables a decrease in traceback length, the problem of decreasing access times for path storage still remains.